10107. Найти медиану

Медианой последовательности называется число, которое делит ее на две равные части. Например, для {1, 3, 6, 2, 7}медианой будет число 3, так как слева от него расположены {1, 2}, а справа {6, 7}. В случае четного количества чисел в последовательности в качестве медианы выбирается среднее арифметическое средних чисел. Например, для {1, 3, 6, 2, 7, 8} средними будут числа 3 и 6, а их среднее арифметическое (а следовательно и медиана) равна (3 + 6) / 2 = 4.5. Выводить следует только целую часть медианы.

Вход. Состоит из не более чем 10000 чисел, каждое из которых является целым в диапазоне от 0 до 2³¹.

Выход. Для каждого входного числа вывести медиану текущей считанной последовательности. Для каждого значения медианы выводить только ее целую часть.

Пример входа

1

3

4

60

70

50

2

Пример выхода

1

2

3

3

4

27

4

РЕШЕНИЕ

поиск

Анализ алгоритма

Начиная с пустой последовательности, будем вставлять в нее текущие числа так, чтобы текущая последовательность оставалась отсортированной. Тогда ее медиана считается за константное время. Динамически поддерживаемую последовательность храним в структуре данных vector. Позицию очередного вставляемого элемента ищем при помощи функции lower_bound.

Реализация алгоритма

В динамическом массиве v типа vector будем хранить текущую считанную отсортированную по возрастанию последовательность. В переменной len храним длину текущей последовательности (количество считанных входных чисел).

vector<int> v;

int n, pos, len = 0;

Для каждого нового числа n при помощи функции lower_bound находим позицию pos, на которую можно вставить число n так, чтобы не нарушалось свойство отсортированности массива.

while(scanf("%d",&n) == 1)

{

len++;

pos = lower_bound(v.begin(),v.end(),n) - v.begin();

Вставляем число n в позицию pos.

v.insert(v.begin()+pos,n);

В зависимости от длины последовательности выводим значение ее медианы. Последняя равна v[len / 2], если количество чисел в последовательности нечетно и (v[len / 2] + v[len / 2 – 1]) / 2 иначе.

if (len & 1) printf("%d\n",v[len/2]);

else printf("%d\n",(v[len/2] + v[len/2-1])/2);

}

Реализация алгоритма – итераторы, O(n logn)

#include <cstdio>

#include <set>

using namespace std;

int n, size;

multiset<int> s;

multiset<int>::iterator iter, iter1;

int main(void)

{

scanf("%d",&n);

s.insert(n); iter = s.begin();

printf("%d\n",n);

size = 1;

while(scanf("%d",&n) == 1)

{

s.insert(n); size++;

if ((n < *iter) && (size % 2 == 0)) iter--;

if ((n >= *iter) && (size % 2 == 1)) iter++;

if (size & 1) printf("%d\n",*iter);

else

{

iter1 = iter; iter1++;

printf("%d\n",(*iter + *iter1)/2);

}

}

return 0;

}